#ifndef __DULKLIST_H
#define __DULKLIST_H

#include <iostream>
#include <fstream>
#include <cassert>
#include <cstdlib>
#include "iofile.h"
using namespace std;

/*
 * The definition of node of double linked list.
 */
template <typename T, typename K>
class _dulklist
{
public:
    K key;
    T *prev, *next;
};

/*
 * For double linked list.
 */
template <typename T>
void dulklist_init(T *&head)
{
    head = NULL;
}

template <typename T, typename K>
void dulklist_create(T *&head)
{
    T **p, *q;
    int n;

    dulklist_init(head);
    p = &head;
    q = head;
    input >> n;
    for (int i = 0; i < n; i++) {
        K t;
        input >> t;
        *p = new T;
        assert(p);
        (*p)->key = t;
        (*p)->prev = q;
        (*p)->next = NULL;
        q = *p;
        p = &(*p)->next;
    }
}

template <typename T>
void dulklist_destory(T *&head)
{
    T *p;

    while (head) {
        p = head;
        head = head->next;
        delete p;
    }
}

template <typename T>
void dulklist_print(T *head)
{
    T *p = head, *q = NULL;

    while (p) {
        cout << p->key << " ";
        q = p;
        p = p->next;
    }
    cout << endl;
    while (q) {
        cout << q->key << " ";
        q = q->prev;
    }
    cout << endl;
}

/*
 * For double linked list with cycle.
 */
template <typename T>
void dulklist_init_cycle(T *&head)
{
    head = NULL;
}

template <typename T, typename K>
void dulklist_create_cycle(T *&head)
{
    T **p, *q;
    int n;

    dulklist_init_cycle(head);
    p = &head;
    q = head;
    input >> n;
    for (int i = 0; i < n; i++) {
        K t;
        input >> t;
        *p = new T;
        assert(p);
        (*p)->key = t;
        (*p)->prev = q;
        (*p)->next = head;
        q = *p;
        p = &(*p)->next;
    }
    if (head)
        head->prev = q;
}

template <typename T>
void dulklist_destory_cycle(T *&head)
{
    T *p, *q;

    if (head) {
        p = head;
        do {
            q = p;
            p = p->next;
            delete q;
        } while (p != head);
        head = NULL;
    }
}

template <typename T>
void dulklist_print_cycle(T *head)
{
    T *p;

    if (head) {
        p = head;
        do {
            cout << p->key << " ";
            p = p->next;
        } while (p != head);
        cout << endl;
        p = head->prev;
        do {
            cout << p->key << " ";
            p = p->prev;
        } while (p != head->prev);
        cout << endl;
    }
}

/*
 * For double linked list with head.
 */
template <typename T>
void dulklist_init_head(T *&head)
{
    head = new T;
    assert(head);
    head->prev = head->next = NULL;
}

template <typename T, typename K>
void dulklist_create_head(T *&head)
{
    T **p, *q;
    int n;

    dulklist_init_head(head);
    p = &head->next;
    q = head->next;
    input >> n;
    for (int i = 0; i < n; i++) {
        K t;
        input >> t;
        *p = new T;
        assert(p);
        (*p)->key = t;
        (*p)->prev = q;
        (*p)->next = NULL;
        q = *p;
        p = &(*p)->next;
    }
}

template <typename T>
void dulklist_destory_head(T *&head)
{
    T *p;

    while (head->next) {
        p = head->next;
        head->next = head->next->next;
        delete p;
    }
    delete head;
    head = NULL;
}

template <typename T>
void dulklist_print_head(T *head)
{
    T *p = head->next, *q = NULL;

    while (p) {
        cout << p->key << " ";
        q = p;
        p = p->next;
    }
    cout << endl;
    while (q) {
        cout << q->key << " ";
        q = q->prev;
    }
    cout << endl;
}

/*
 * For double linked list with head and cycle.
 */
template <typename T>
void dulklist_init_head_cycle(T *&head)
{
    head = new T;
    assert(head);
    head->prev = head->next = head;
}

template <typename T, typename K>
void dulklist_create_head_cycle(T *&head)
{
    T **p, *q;
    int n;

    dulklist_init_head_cycle(head);
    p = &head->next;
    q = head->next;
    input >> n;
    for (int i = 0; i < n; i++) {
        K t;
        input >> t;
        *p = new T;
        assert(p);
        (*p)->key = t;
        (*p)->prev = q;
        (*p)->next = head;
        q = *p;
        p = &(*p)->next;
    }
    if (head)
        head->prev = q;
}

template <typename T>
void dulklist_destory_head_cycle(T *&head)
{
    T *p, *q;

    p = head->next;
    while (p != head) {
        q = p;
        p = p->next;
        delete q;
    }
    delete head;
    head = NULL;
}

template <typename T>
void dulklist_print_head_cycle(T *head)
{
    T *p = head->next;

    while (p != head) {
        cout << p->key << " ";
        p = p->next;
    }
    cout << endl;
    p = head->prev;
    while (p != head) {
        cout << p->key << " ";
        p = p->prev;
    }
    cout << endl;
}

#endif

